<HTML><HEAD><TITLE>minimum_spanning_tree(+Graph, +DistanceArg, -Tree, -TreeWeight)</TITLE>
</HEAD><BODY>[ <A HREF="index.html">library(graph_algorithms)</A> | <A HREF="../../index.html">Reference Manual</A> | <A HREF="../../fullindex.html">Alphabetic Index</A> ]
<H1>minimum_spanning_tree(+Graph, +DistanceArg, -Tree, -TreeWeight)</H1>
Computes a minimum spanning tree and its weight
<DL>
<DT><EM>Graph</EM></DT>
<DD>a graph structure
</DD>
<DT><EM>DistanceArg</EM></DT>
<DD>which argument of EdgeData to use as distance: integer
</DD>
<DT><EM>Tree</EM></DT>
<DD>a list of e/3 edge structures
</DD>
<DT><EM>TreeWeight</EM></DT>
<DD>sum of the tree's edge weights: number
</DD>
</DL>
<H2>Description</H2>
<P>
    Computes a minimum spanning tree for the given graph. A minimum
    spanning tree is a smallest subset of the graph's edges that still
    connects all the graph's nodes. Such a tree is not unique and of
    course exists only if the original graph is itself connected.
    However, all minimum spanning trees will have the same cost.
</P><P>
    The computed tree is returned in Tree, which is simply a list of
    the edges that form the tree. The TreeWeight is the total length
    of the tree's edges, according to DistanceArg.
</P><P>
    DistanceArg refers to the graph's EdgeData information that was
    specified when the graph was constructed. If EdgeData is a simple
    number, then DistanceArg should be 0 and EdgeData will be taken
    as the length of the edge. If EdgeData is a compound data structure,
    DistanceArg should be a number between 1 and the arity of that
    structure and determines which argument of the EdgeData structure
    will be interpreted as the edge's length. Important: the distance
    information in EdgeData must be a non-negative number, and the
    numeric type (integer, float, etc) must be the same in all edges.
</P><P>
    If DistanceArg is given as -1, then any EdgeData is ignored and
    the length of every edge is assumed to be equal to 1.
</P><P>
    The direction of the graph's edges is ignored by this predicate.
</P><P>
    The implementation uses Kruskal's algorithm which has a complexity
    of O(Nedges*log(Nedges)).
    </P>
<H3>Modes and Determinism</H3><UL>
<LI>minimum_spanning_tree(+, +, -, -) is semidet
</UL>
<H3>Fail Conditions</H3>
No spanning tree exists, i.e. the graph is not connected.
<H2>Examples</H2>
<PRE>
    ?- sample_graph(G), minimum_spanning_tree(G, 0, T, W).
    T = [e(2, 10, 1), e(4, 8, 1), e(9, 2, 1), e(7, 3, 2), ...]
    W = 16
    </PRE>
<H2>See Also</H2>
<A HREF="../../lib/graph_algorithms/minimum_spanning_forest-5.html">minimum_spanning_forest / 5</A>
</BODY></HTML>
